package com.zlk.algorithm.algorithm.dynamicPlan;

import java.util.Arrays;

// 解码方法 II
// 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 一条已编码的消息，所有的数字都必须分组
// 然后按原来的编码方案反向映射回字母（可能存在多种方式）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
// 除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
// 可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
// 例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
// 对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
// 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目
// 由于答案数目可能非常大，返回10^9 + 7的模
// 测试链接 : https://leetcode.cn/problems/decode-ways-ii/
public class Code04_DecodeWaysII {

    public int numDecodings(String s) {
//        char[] chars = s.toCharArray();
//        return f1My(0,chars);
        char[] chars = s.toCharArray();
        long[] dp = new long[chars.length];
        Arrays.fill(dp, -1);
        return (int) f2(chars, 0, dp);
    }



    public static long mod = 1000000007;
    /**
     * 为 0
     *
     * 不为 0
     * 报错 todo
     * @param i
     * @param chars
     * @return
     */
    private int f1My(int i,char[] chars) {
        if(i>=chars.length){//
            return 1;
        }
        //为0
        if(chars[i]=='0'){
            return 0;
        }else{
            //不为0
            //1、自己为一个数
            //   自己数是* 自己数不是*
            //2、自己和下一个位置为一个数
            //   下一个位置是* 下一个位置不是*
            int res = 0;
            if(chars[i]=='*'){
                //当前位置是*
                // 自己为一个数
                res+=9*f1My(i+1,chars);
                //自己不为一个数，下一个位置不是*
                if(i + 1 < chars.length&&chars[i+1]!='*'){
                    if(chars[i+1]>'6'){
                        res+=f1My(i+2,chars);
                    }else{
                        res+=2*f1My(i+2,chars);
                    }
                }else{
                    if(i + 1 < chars.length){
                        //下一个位置也是*
                        // 1*9    2：1  2：2 2:3 2:4 2:5 2:6
                        res+=15*f1My(i+2,chars);
                    }
                }
            }else{
                //自己不为*
                res+=f1My(i+1,chars);
                //自己不为一个数，下一个位置不是*
                if(i+1<chars.length&&chars[i+1]!='*'){
                    if (i + 1 < chars.length && ((chars[i] - '0') * 10 + chars[i + 1] - '0') <= 26) {
                        res+=f1My(i+2,chars);
                    }
                }else{
                    //下一个位置为*
                    if(i + 1 < chars.length&&chars[i]=='2'){
                        res+=6*f1My(i+2,chars);;
                    }
                    if(i + 1 < chars.length&&chars[i]=='1'){
                        res+=9*f1My(i+2,chars);;
                    }
                }
            }

            res %= mod;
            return res;
        }
    }



    private long f1My2(int i,char[] chars,long[] dp) {
        if(i>=chars.length){//
            return 1;
        }
        //为0
        if(chars[i]=='0'){
            return 0;
        }else{
            //不为0
            //1、自己为一个数
            //   自己数是* 自己数不是*
            //2、自己和下一个位置为一个数
            //   下一个位置是* 下一个位置不是*
            long res = 0;
            if(dp[i]!=-1){
                return dp[i];
            }
            if(chars[i]=='*'){
                //当前位置是*
                // 自己为一个数
                res+=9*f1My2(i+1,chars,dp);
                //自己不为一个数，下一个位置不是*
                if(i + 1 < chars.length&&chars[i+1]!='*'){
                    if(chars[i+1]>'6'){
                        res+=f1My2(i+2,chars,dp);
                    }else{
                        res+=2*f1My2(i+2,chars,dp);
                    }
                }else{
                    if(i + 1 < chars.length){
                        //下一个位置也是*
                        // 1*9    2：1  2：2 2:3 2:4 2:5 2:6
                        res+=15*f1My2(i+2,chars,dp);
                    }
                }
            }else{
                //自己不为*
                res+=f1My2(i+1,chars,dp);
                //自己不为一个数，下一个位置不是*
                if(i+1<chars.length&&chars[i+1]!='*'){
                    if (i + 1 < chars.length && ((chars[i] - '0') * 10 + chars[i + 1] - '0') <= 26) {
                        res+=f1My2(i+2,chars,dp);
                    }
                }else{
                    //下一个位置为*
                    if(i + 1 < chars.length&&chars[i]=='2'){
                        res+=6*f1My2(i+2,chars,dp);
                    }
                    if(i + 1 < chars.length&&chars[i]=='1'){
                        res+=9*f1My2(i+2,chars,dp);
                    }
                }
            }

            res %= mod;
            dp[i] =res;
            return res;
        }
    }


    public int f1(char[] s, int i) {
        if (i == s.length) {
            return 1;
        }
        if (s[i] == '0') {
            return 0;
        }
        // s[i] != '0'
        // 2) i想单独转
        int ans = f1(s, i + 1) * (s[i] == '*' ? 9 : 1);
        // 3) i i+1 一起转化 <= 26
        if (i + 1 < s.length) {
            // 有i+1位置
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // num num
                    //  i  i+1
                    if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // num  *
                    //  i  i+1
                    if (s[i] == '1') {
                        ans += f1(s, i + 2) * 9;
                    }
                    if (s[i] == '2') {
                        ans += f1(s, i + 2) * 6;
                    }
                }
            } else {
                if (s[i + 1] != '*') {
                    // *  num
                    // i  i+1
                    if (s[i + 1] <= '6') {
                        ans += f1(s, i + 2) * 2;
                    } else {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // *  *
                    // i  i+1
                    // 11 12 ... 19 21 22 ... 26 -> 一共15种可能
                    // 没有10、20，因为*只能变1~9，并不包括0
                    ans += f1(s, i + 2) * 15;
                }
            }
        }
        return ans;
    }


    long f2(char[] s, int i,long[] dp) {
        if (i == s.length) {
            return 1;
        }
        if (s[i] == '0') {
            return 0;
        }

        if(dp[i]!=-1){
            return dp[i];
        }
        // s[i] != '0'
        // 2) i想单独转
        long ans = f2(s, i + 1,dp) * (s[i] == '*' ? 9 : 1);
        // 3) i i+1 一起转化 <= 26
        if (i + 1 < s.length) {
            // 有i+1位置
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // num num
                    //  i  i+1
                    if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
                        ans += f2(s, i + 2,dp);
                    }
                } else {
                    // num  *
                    //  i  i+1
                    if (s[i] == '1') {
                        ans += f2(s, i + 2,dp) * 9;
                    }
                    if (s[i] == '2') {
                        ans += f2(s, i + 2,dp) * 6;
                    }
                }
            } else {
                if (s[i + 1] != '*') {
                    // *  num
                    // i  i+1
                    if (s[i + 1] <= '6') {
                        ans += f2(s, i + 2,dp) * 2;
                    } else {
                        ans += f2(s, i + 2,dp);
                    }
                } else {
                    // *  *
                    // i  i+1
                    // 11 12 ... 19 21 22 ... 26 -> 一共15种可能
                    // 没有10、20，因为*只能变1~9，并不包括0
                    ans += f2(s, i + 2,dp) * 15;
                }
            }
        }
        ans %=mod;
        dp[i]= ans;
        return ans;
    }

    int f3(char[] s) {
        long[] dp = new long[s.length+1];
        Arrays.fill(dp,-1);

        dp[s.length] = 1;
        for (int i = s.length-1; i >= 0; i--) {
            if(s[i]=='0'){
                dp[i] = 0;
            }else{
                long ans = dp[i+1] * (s[i] == '*' ? 9 : 1);
                // 3) i i+1 一起转化 <= 26
                if (i + 1 < s.length) {
                    // 有i+1位置
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            // num num
                            //  i  i+1
                            if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
                                ans += dp[i+2];
                            }
                        } else {
                            // num  *
                            //  i  i+1
                            if (s[i] == '1') {
                                ans += dp[i+2] * 9;
                            }
                            if (s[i] == '2') {
                                ans += dp[i+2] * 6;
                            }
                        }
                    } else {
                        if (s[i + 1] != '*') {
                            // *  num
                            // i  i+1
                            if (s[i + 1] <= '6') {
                                ans += dp[i+2] * 2;
                            } else {
                                ans += dp[i+2];
                            }
                        } else {
                            // *  *
                            // i  i+1
                            // 11 12 ... 19 21 22 ... 26 -> 一共15种可能
                            // 没有10、20，因为*只能变1~9，并不包括0
                            ans += dp[i+2] * 15;
                        }
                    }
                }
                ans %=mod;
                dp[i] = ans;
            }
        }
        return (int)dp[0];
    }




}
